// https://leetcode.cn/problems/group-the-people-given-the-group-size-they-belong-to/
// Created by ade on 2022/8/12.
// 输出：[[5],[0,1,2],[3,4,6]]
// 解释：
// 第一组是 [5]，大小为 1，groupSizes[5] = 1。
// 第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
// 第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。
// 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;


class Solution {
public:
    vector <vector<int>> groupThePeople(vector<int> &groupSizes) {
        unordered_map<int, vector<int>> m = {};
        for (int i = 0; i < groupSizes.size(); i++) {
            m[groupSizes[i]].push_back(i);
        }
        // 3:[0,1,2,3,4,6]
        // 1:[5]
        vector <vector<int>> res = {};
        for (auto items : m) {
            if (items.first == items.second.size()) {
                res.push_back(items.second);
            } else {
                int num = items.second.size() / items.first;
                for (int i = 0; i < num; i++) {
                    res.push_back(
                            {items.second.begin() + i * items.first, items.second.begin() + (i + 1) * items.first});
                }
            }
        }
        return res;
    }
};


int main() {
    Solution so;
    vector<int> groups = {3, 3, 3, 3, 3, 1, 3};
    auto res = so.groupThePeople(groups);

    for (auto items:res) {
        for (auto i : items) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}